package day_2022_7_to_8.day48;

/**
 * @author haomin
 * @date 2022/07/21 12:16
 **/
public class Day6_2_Num70_ClimbStairs {
    // 方法一：递归（时间复杂度过大）
    class Solution1 {
        public int climbStairs(int n) {
            if(n == 1) return 1;
            if(n == 2) return 2;

            return climbStairs(n - 1) + climbStairs(n - 2);
        }
    }

    // 方法二：动态规划
    class Solution {
        public int climbStairs(int n) {
            if(n < 3){
                return n;
            }
            int[] dp = new int[n+1];
            dp[1] = 1;
            dp[2] = 2;
            for(int i = 3;i <= n;i++){
                dp[i] = dp[i-1] + dp[i-2];
            }
            return dp[n];
        }
    }
}